package my.algorithms.sort;

import java.util.Arrays;

/**
 * Created by IntelliJ IDEA.
 * User: jtruelove
 * Date: 3/12/11
 * Time: 9:51 AM
 * To change this template use File | Settings | File Templates.
 */
public class SimpleSort
{
    /**
     * Sequence of numbers 0..N-1 where N is the upper bound
     *
     * @param array
     * @param upperBound
     * @return
     */
    public static int [] sortArrayNoDuplicates(int [] array, int upperBound)
    {
        int [] cpyArray = new int [upperBound];
        int [] rtnArray = new int [array.length];

        // pre-populate the array
        Arrays.fill(cpyArray, -1);

        for(int i = 0; i < array.length; i++)
        {
            cpyArray[array[i]] = array[i];
        }

        int i = 0;
        int j = 0;
        while (j < array.length)
        {
           if (cpyArray[i] != -1)
           {
               rtnArray[j] = cpyArray[i];
               j++;
           }
           i++;
        }
        return rtnArray;
    }

    public static int [] sortArrayDuplicates(int [] array, int upperBound)
    {
        int [] cpyArray = new int [upperBound];
        int [] rtnArray = new int [array.length];

        // pre-populate the array
        Arrays.fill(cpyArray, -1);

        for(int i = 0; i < array.length; i++)
        {
            if(cpyArray[array[i]] == -1)
            {
                cpyArray[array[i]] = 1;
            }
            else
            {
                cpyArray[array[i]] += 1;
            }
        }

        int i = 0;
        int j = 0;
        while (i < cpyArray.length)
        {
           if (cpyArray[i] != -1)
           {
               for(int v = 0; v < cpyArray[i]; v++)
               {
                rtnArray[j] = i;
                j++;
               }
           }
           i++;
        }
        return rtnArray;
    }

    public static void printArray(int [] array)
    {
        for (int num : array)
        {
            System.out.print(num + "  ");
        }
        System.out.println();
    }

    public static void main(String [] args)
    {
        //   9 - 5 = 4, 9 -  = 7
        sortArrayNoDuplicates(new int [] {2,5,1,7,6,8,0}, 9);
        printArray (sortArrayNoDuplicates(new int [] {2,5,1,7,6,8,0}, 9));
        printArray (sortArrayDuplicates(new int [] {2,5,5,7,2,8,0}, 9));
    }
}
